package myqueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MyQueue {
    //因为是链表实现，所以需要有节点
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;

    //入队操作
    public void offer (int val){
        ListNode node = new ListNode(val);
        //第一次插入
        if(head == null){
            head = last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }

    //头删
    public int poll() {
        if(head == null){
            return -1;
        }
        int ret = head.val;
        //只有一个节点
        if(head.next == null){
            head = null;
            last = null;
        }else {
            head = head.next;
            head.prev = null;
        }
        return ret;
    }

    public int peek() {
        if (head == null)
            return -1;
        return head.val;
    }

    public boolean isEmpty(){
        return head == null;
    }
}

class MyCircularQueue {

    public int[] elem;
    public int first;
    public int last;


    public MyCircularQueue(int k) {
        elem = new int[k + 1];
    }

    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        elem[last] = value;
        last = (last + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        first = (first + 1) % elem.length;
        return true;
    }

    public int Front() {
        if(isEmpty())
            return -1;
        return elem[first];
    }

    public int Rear() {
        if(isEmpty())
            return -1;
        int index = (last == 0) ? elem.length - 1: last - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        return first == last;
    }

    public boolean isFull() {
        return first == (last + 1) % elem.length;
    }


}




class MyStack {
    //需要两个队列
    public Queue<Integer> queue1;
    public Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }


    /**
     * 入栈
     * @param x
     */
    public void push(int x) {
        if(empty()){
            queue1.offer(x);
            return;
        }
        if(!queue1.isEmpty()){
           queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

    /**
     * 出栈
     * @return
     */
    public int pop() {
        if (empty()) {
            return -1;
        }
        if (queue1.isEmpty()) {
            int size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        } else {
            int size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }
    }

    /**
     * 获取栈顶元素
     * @return
     */
    public int top() {
        if (empty()) {
            return -1;
        }
        if (queue1.isEmpty()) {
            int size = queue2.size();
            int ret = -1;
            for (int i = 0; i < size - 1; i++) {
                ret = queue2.poll();
                queue1.offer(ret);
            }
            return ret;
        } else {
            int size = queue1.size();
            int ret = -1;
            for (int i = 0; i < size - 1; i++) {
                ret = queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        }
    }

    /**
     * 判断栈空不空
     * @return
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

class MyQueue1 {
    public Stack<Integer> s1;
    public Stack<Integer> s2;

    public MyQueue1() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
}
   /* public void push(int x) {
        s1.push(x);
    }*/

    /*public int pop() {
        if(s2.isEmpty()){
            while( !s1.isEmpty()){
                s2.push(s1.pop());
            }
        }return s2.pop();
    }

    public int peek() {

    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}*/









